1. Field of the Invention
The present invention relates to a circuit synthesis method for an LSI for automatically generating a logic circuit of a register transfer level (RTL) from a behavioral description, and specifically to a high level synthesis method which is especially effective for designing devices which need to be designed within a short period of time such as, for example, ASICs (Application Specific Integrated Circuits).
2. Description of the Related Art
High level synthesis is a technology for automatically generating an RTL logic circuit from a behavioral description which describes only a behavior of calculation processing and does not include information on a hardware structure. High level synthesis is described in detail in Deniel Gajski, Allen Wu, Nikil Dutt and Steve Lin, xe2x80x9cHigh-Level Synthesisxe2x80x9d published by Kluwer Academic Publishers, 1992. High level synthesis is also disclosed in Japanese Laid-Open Publication No. 5-101141. High level synthesis will be described briefly below.
 less than Conversion of Behavioral Description into CDFG greater than 
In high level synthesis, a behavioral description describing only a behavior of calculation processing is analyzed, and then the behavioral description is converted into a model referred to as a control data flowgraph (CDFG) representing the dependency among the calculations, i.e., the execution order of the calculations.
For example, a behavioral description of expression (1) is converted into a CDFG in the following manner.
f={(a*b)+c+d)}/exe2x80x83xe2x80x83(1)
A CDFG is a graph in which calculations, inputs and outputs are represented by nodes, and data dependency (i.e., execution order of calculations, inputs and outputs) is represented by directional edges (data dependency edges; e.g., arrows). For example, in FIG. 1, which illustrates a CDFG 100 corresponding to the behavioral description of expression (1), a data dependency edge 15 indicates that an addition 5 is performed after a multiplication 4 is performed. In the CDFG 100, inputs xe2x80x9caxe2x80x9d, xe2x80x9cbxe2x80x9d, xe2x80x9ccxe2x80x9d, xe2x80x9cdxe2x80x9d and xe2x80x9cexe2x80x9d are respectively represented by reference numerals 28 through 32, and an output xe2x80x9cfxe2x80x9d is represented by reference numeral 33. As mentioned above, the multiplication (xe2x80x9c*xe2x80x9d) is represented by reference numeral 4, and additions (xe2x80x9c+xe2x80x9d) are represented by reference numerals 5 and 6. A division (xe2x80x9c/xe2x80x9d) is represented by reference numeral 7. In this specification, symbol xe2x80x9c*xe2x80x9d indicates multiplication.
A data dependency edge from the input xe2x80x9caxe2x80x9d 28 to the multiplication 4 is represented by reference numeral 13. A data dependency edge from the input xe2x80x9cbxe2x80x9d 29 to the amultiplication 4 is represented by reference numeral 14. A data dependency edge from the multiplication 4 to the addition 5 is represented by reference numeral 15. A data dependency edge from the input xe2x80x9ccxe2x80x9d 30 to the addition 5 is represented by reference numeral 16. A data dependency edge from the addition 5 to the addition 6 is represented by reference numeral 17. A data dependency edge from the input xe2x80x9cdxe2x80x9d 31 to the addition 6 is represented by reference numeral 18. A data dependency edge from the addition 6 to the division 7 is represented by reference numeral 19. A data dependency edge from the input xe2x80x9cexe2x80x9d 32 to the division 7 is represented by reference numeral 20. A data dependency edge from the division 7 to the output xe2x80x9cfxe2x80x9d 33 is represented by reference numeral 21.
 less than Scheduling greater than 
After the behavioral description of expression (1) is converted into the CDFG 100 (FIG. 1), scheduling is performed. Scheduling is processing for assigning each of the calculations, inputs and the output to a time slot. (The CDFG 100 (FIG. 1) includes only one output.) Each time slot corresponds to a state of a finite state machine and is referred to as a scheduling step.
FIG. 2 shows a scheduling result 110 obtained as a result of scheduling the CDFG 100 (FIG. 1). Here, a delay time period determined by the multiplication 4 is 50 ns, a delay time period determined by each of the additions 5 and 6 is 10 ns, a delay time period determined by the division 7 is 60 ns, and a clock cycle in each scheduling step is 100 ns.
Scheduling is performed so that the total of the delay time periods of the calculations, which are connected by data dependency edges and scheduled in one scheduling step, does not exceed one clock cycle. For example, in FIG. 2, the total of the delay time periods determined by the multiplication 4, the additions 5 and 6, and the division 7 is 50+10+10+60=130 ns. Accordingly, these four calculations cannot be scheduled in one scheduling step.
In FIG. 2, the input xe2x80x9caxe2x80x9d 28 and the input xe2x80x9cbxe2x80x9d 29 are scheduled in scheduling step 0. The multiplication 4, the input xe2x80x9ccxe2x80x9d 30, the addition 5 and the input xe2x80x9cdxe2x80x9d 31 are scheduled in scheduling step 1. The addition 6, the input xe2x80x9cexe2x80x9d 32 and the division 7 are scheduled in scheduling step 2. Only the output xe2x80x9cfxe2x80x9d 33 is scheduled in scheduling step 3.
The same type of calculations scheduled in different scheduling steps can share one calculation device. In FIG. 2, the addition 5 and the addition 6 are respectively scheduled in scheduling steps 1 and 2, and therefore can share one calculation device. By scheduling, each of the calculations is assigned to an appropriate scheduling step so as to minimize the cost of the hardware.
In the scheduling result 110 shown in FIG. 2, the data dependency edges 13 and 14 cross the clock boundary between scheduling steps 0 and 1. The data dependency edges 17 and 18 cross the clock boundary between scheduling steps 1 and 2. The data dependency edge 21 crosses the clock boundary between scheduling steps 2 and 3.
 less than Allocation greater than 
Allocation is processing for allocating calculation devices, registers, and input and output pins required to execute the scheduled CDFG; and assigning the calculations of the CDFG to the calculation devices, assigning the data dependency edges crossing the clock boundaries between two adjacent scheduling steps to the registers, and assigning the inputs and outputs to the input and output pins. (Only one output is necessary for the CDFG 100 in FIG. 1.)
FIGS. 3, 4 and 5 show allocation procedures 120, 121 and 122 performed on the CDFG 100 (FIG. 1) scheduled as shown in FIG. 2. FIG. 3 shows an allocation procedure 120 for the calculation devices; FIG. 4 shows an allocation procedure 121 for the registers; and FIG. 5 shows an allocation procedure 122 for the inputs and the output.
By the allocation procedure 120 for the calculation devices shown in FIG. 3, one multiplier 8 (xe2x80x9cmult 1xe2x80x9d), one adder 9 (xe2x80x9cadder 1xe2x80x9d), and one divider 10 (xe2x80x9cdiv 1xe2x80x9d) are allocated. The multiplication 4 in the CDFG 100 is assigned to the multiplier 8. The additions 5 and 6 scheduled in different scheduling steps are assigned to the one adder 9. The division 7 is assigned to the divider 10.
By the allocation procedure 121 for the registers shown in FIG. 4, a first register 11 (xe2x80x9creg 1xe2x80x9d) and a second register 12 (xe2x80x9creg 2xe2x80x9d) are allocated. One of the data dependency edges crossing the clock boundary between scheduling steps 0 and 1 (data dependency edge 13), one of the data dependency edges crossing the clock boundary between scheduling steps 1 and 2 (data dependency edge 17), and the data dependency edge 21 crossing the clock boundary between scheduling steps 2 and 3 are assigned to the first register 11. The other data dependency edge crossing the clock boundary between scheduling steps 0 and 1 (data dependency edge 14) and the other data dependency edge crossing the clock boundary between scheduling steps 1 and 2 (data dependency edge 18) are assigned to the second register 12.
By the allocation procedure 122 for the inputs and output shown in FIG. 5, five input pins xe2x80x9caxe2x80x9d 22, xe2x80x9cbxe2x80x9d 23, xe2x80x9ccxe2x80x9d 24, xe2x80x9cdxe2x80x9d 25, and xe2x80x9cexe2x80x9d 26, and one output pin xe2x80x9cfxe2x80x9d 27 are allocated. The input xe2x80x9caxe2x80x9d 28 is assigned to the input pin xe2x80x9caxe2x80x9d 22, the input xe2x80x9cbxe2x80x9d 29 is assigned to the input pin xe2x80x9cbxe2x80x9d 23, the input xe2x80x9ccxe2x80x9d 30 is assigned to the input pin xe2x80x9ccxe2x80x9d 24, the input xe2x80x9cdxe2x80x9d 31 is assigned to the input pin xe2x80x9cdxe2x80x9d 25, and the input xe2x80x9cexe2x80x9d 32 is assigned to the input pin xe2x80x9cexe2x80x9d 26. The output xe2x80x9cfxe2x80x9d 33 is assigned to the output pin xe2x80x9cfxe2x80x9d 27.
 less than Data Path Generation greater than 
Data path generation is processing for generating circuit paths corresponding to the data dependency edges in the CDFG. FIG. 6 shows an exemplary data path generation result 130 obtained as a result of the data path generation performed on the CDFG 100 (FIG. 1).
For the calculation devices, registers or the like which are shared, a multiplexer is allocated for selecting data to be input to the calculation devices, registers or the like. In FIG. 6, a first multiplexer 41 (xe2x80x9cmux 1xe2x80x9d) is allocated for the first register 11, and a second multiplexer 42 (xe2x80x9cmux 2xe2x80x9d) is allocated for the second register 12. A third multiplexer 43 (xe2x80x9cmux 3xe2x80x9d) and a fourth multiplexer 44 (xe2x80x9cmux 4xe2x80x9d) are allocated for the adder 9.
A data path which corresponds to a path from the input xe2x80x9caxe2x80x9d 28 through the data dependency edge 13 to the multiplication 4 is generated by first generating a path from the input pin xe2x80x9caxe2x80x9d 22 through the first multiplexer 41 to the first register 11 and then generating a path from the first register 11 to the multiplier 8. Other data paths are generated in a similar manner.
 less than Controller Generation greater than 
Controller generation is processing for generating a controller for controlling the calculation devices, registers and multiplexers allocated by the allocation and the data path generation.
FIG. 7 shows an exemplary controller generation result 140 obtained as a result of generating a controller 50. The controller 50 controls the first and second multiplexers 41 and 42, the first and second registers 11 and 12, and third and fourth multiplexers 43 and 44.
As described above, in high level synthesis, a plurality of calculations connected by data dependency edges can be scheduled in one scheduling step and can share one calculation device. In such high level synthesis, data paths generated by the data path generation include true paths. However, the data paths may undesirably include a false path. A true path is a data path which becomes entirely active in either one of scheduling steps; and a false path is a data path which does not become entirely active in either one of scheduling steps. The false path is formed by a combination of portions of true paths.
FIG. 8 shows an exemplary data path generation result 150 obtained for the CDFG 100 (FIG. 1). In the data path generation result 150, a data path 47 from the first register 11xe2x80x94the multiplier 8xe2x80x94the third multiplexer 43xe2x80x94the adder 9xe2x80x94the divider 10xe2x80x94the first multiplexer 41 to the first register 11 is generated as a false path. The false path 47 causes a delay time period of 120 ns. The false path 47 is formed by combining a portion of each of the following two true paths. One true path is: the first register 11xe2x80x94the multiplier 8xe2x80x94the third multiplexer 43xe2x80x94the adder 9xe2x80x94the first multiplexer 41xe2x80x94the first register 11. The other true path is: the first register 11xe2x80x94the third multiplexer 43xe2x80x94the adder 9xe2x80x94the divider 10xe2x80x94the first multiplexer 41xe2x80x94the first register 11. A portion from the first true path: the first register 11xe2x80x94the multiplier 8xe2x80x94the third multiplexer 43xe2x80x94the adder 9 is combined with a portion from the second true path: the adder 9xe2x80x94the divider 10xe2x80x94the first multiplexer 41xe2x80x94the first register 11. Thus, the false path 47 is formed.
Even when such a false path is generated and the delay time period determined by the false path exceeds the clock cycle, the logic circuit normally operates. The reason is that the false path does not become entirely active in either one of scheduling steps.
However, a logic synthesis tool cannot usually determine which data path is a true path and which path is a false path. Accordingly, in logic synthesis, the delay time period of a false path which does not need to be optimized is optimized like a true path so that the delay time period does not exceed the clock cycle. This results in enlargement of the size of the logic circuit. In addition, when the delay time period of a path exceeds the clock cycle as a result of logic synthesis, the logic synthesis tool incorrectly determines that the condition for the delay time period is not fulfilled even when that path is a false path, and operates abnormally.
According to one aspect of the invention, a circuit synthesis method, comprising the steps of converting a behavioral description describing a behavior of calculation processing into a control data flowgraph; assigning at least one calculation, at least one input and at least one output in the control data flowgraph into prescribed time slots: assigning the at least one calculation, a plurality of data dependency edges, the at least one input and the at least one output respectively to at least one calculation device, at least one register, at least one input pin and at least one output pin; generating a plurality of paths corresponding to the plurality of data dependency edges; and detecting a first false path among the plurality of paths.
In one embodiment of the invention, the step of detecting the first false path among the plurality of paths includes the step of detecting, among at least one first path formed by combining at least a portion of at least one true path generated by the plurality of paths, a second path, which is not a true path, as the first false path.
In one embodiment of the invention, the step of detecting the first false path among the plurality of paths includes the steps of detecting at least one third path including one of the at least one calculation device, among the at least one true path; dividing the at least one third path into a plurality of portions: detecting at least one fourth path formed by combining the plurality of portions of the at least one third path; and detecting, among the at least one fourth path, a fifth path, which is not a true path, as the first false path.
In one embodiment of the invention, the circuit synthesis method further includes the steps of detecting at least one sixth path including the one of the at least one calculation device, among the at least one true path and the first false path; dividing the at least one sixth path into a plurality of portions; detecting at least one seventh path formed by combining the plurality of portions of the at least one sixth path; and detecting, among the at least one seventh path, an eighth path, which is not a true path, as a second false path.
In one embodiment of the invention, the circuit synthesis method further includes the step of estimating a delay time period occurring in logic synthesis, ignoring the first false path.
In one embodiment of the invention, the circuit synthesis method further includes the step of estimating a delay time period occurring in logic synthesis, ignoring information on the second false path.
According to another aspect of the invention, a recording medium having a program written thereon for causing a computer to execute circuit synthesis is provided. The circuit synthesis is performed by a method including the steps of converting a behavioral description describing a behavior of calculation processing into a control data flowgraph; assigning each of at least one calculation, at least one input and at least one output in the control data flowgraph into a prescribed time slot; assigning the at least one calculation, a plurality of data dependency edges, the at least one input and the at least one output respectively to at least one calculation device, at least one register, at least one input pin and at least one output pin; generating a plurality of paths corresponding to the plurality of data dependency edges; and detecting a first false path among the plurality of paths.
Thus, the invention described herein makes possible the advantages of providing a circuit synthesis method for preventing a logic synthesis tool from optimizing the delay time period of a false path and preventing the logic synthesis tool from operating abnormally by determining that the condition for the delay time period is not fulfilled when a delay time period determined by the false path exceeds a clock cycle.
These and other advantages of the present invention will become apparent to those skilled in the art upon reading and understanding the following detailed description with reference to the accompanying figures.